904. 水果成篮

Similar Question

Solution Tips

方案一: 滑动窗口 + 哈希 Map

var totalFruit = function(fruits) {
    // 只有两个篮子, 固定的2个
    // 每次只能摘一个, 那就是要找 连续的 2种果树, 最长
    // 滑动窗口, 控制始终只有2种果树
    let left = 0;
    let right = 0;

    let res = 0;
    let count = 0;
    const bucket = new Map();
    while (left <= right && right < fruits.length) {
        while (bucket.size <= 2 && right < fruits.length) {
            if (bucket.has(fruits[right])) {
                // 已有品种的水果, 扩大 right , 搜集水果
                bucket.set(fruits[right], bucket.get(fruits[right]) + 1);
                right++;
                count++;
            }
            else {
                // 新品种的水果
                if (bucket.size <= 1) {
                    // 放入新水果
                    bucket.set(fruits[right], 1);
                    right++;
                    count++;
                }
                else {
                    // 退出循环
                    break;
                }
            }
        }
        // 下一个 right 就是新品种的水果了
        // 更新 res
        res = Math.max(res, count);

        // 必须把 bucket 清理到只剩下一种水果
        while (bucket.size === 2 && left <= right) {
            bucket.set(fruits[left], bucket.get(fruits[left]) - 1);
            if (bucket.get(fruits[left]) === 0) {
                bucket.delete(fruits[left]);
            }
            left++;
            count--;
        }
    }

    return res;
};